Distributed packet switched networks, including local area networks (LANs), wide area networks (WANs), metropolitan area networks (MANs), and the Internet, for example, are comprised of nodes interconnected by various transmission media. The nodes may include one or more edge devices, switches, routers, gateways, hubs, and network management systems, for example, that exchange data as well as control messages. Included in the set of control messages are the messages used to perform various switching and management functions that require knowledge of the topology of the network.
Some of the relatively more intelligent nodes are enabled with discovery processing, e.g., an adjacency detection protocol, able to detect the presence of other devices and even some operational parameters of those devices. Such network devices, herein referred to as adjacency-detection-enabled (ADE) network devices or ADE nodes, generate what are termed discovery messages to prompt similarly enabled devices to respond with identifying information. The reply to a discovery message, termed a discovery response message, generally includes the media access control (MAC) address of the responding device and the port on which the responding device received the message. A suitably enabled network device like an ADE LAN switching device, for example, periodically transmits discovery messages on each of its local ports in order to compile a database of forwarding information for the devices in proximity to the switching device.
Upon receipt of a discovery response message, a LAN switching device generally updates its adjacency table including a list of adjacent ADE devices organized as a function of the local port number. In general, two switches are adjacent if, and only if, the following two requirements are satisfied: (a) there exists a Spanning Tree path between them; and (b) there exists no ADE switch between the two switches on that Spanning Tree path.
Under most circumstances, there is a one-to-one correspondence between the local port and the adjacent device, giving rise to a single entry per port listed in the adjacency table. If there is a hub directly coupled to the local port, however, the adjacency detection software of the switch registers all those ADE devices connected to the hub as being connected to the port of the switch connected to the hub. This results in multiple entries in the adjacency table for each local port connected to the hub. The hubs themselves generally cannot be detected in a network using communication protocols, because they are passive devices that merely forward the incoming discovery messages to all other devices to which it is connected.
The adjacency tables of the various ADE network devices may also be collected by the network management system (NMS) and used to construct a visual display of the network topology. The topology display is a graphical representation that depicts the various ADE network devices interconnected by links derived from the adjacency tables of the devices themselves.
In the prior art however, the graphical representation of the network topology may differ substantially from the physical topology due to the multiplicity of apparent links between the local port of a device and the plurality of other ADE network devices indirectly coupled to the local port through the hub. As a result, the topology display may be both misleading and overly complex. A graphical display of a network topology including n switches, for example, operatively connected to a central hub by means of a single link appears as though each switch is directly linked to each of the other the (n−1) devices. In total, the topology display of such a network includes n×(n−1)/2 links in the network, substantially more than the actual n physical links.
As illustrated in the prior art example of FIG. 1, a topology 100 including n=6 ADE network devices 102 through 112, gives rise to fifteen apparent links that radiate from each of the switches directly linked to a hub (not illustrated). Not only does the apparent links 120A-120E misrepresent the total number of physical links in the subnet, but the physical presence of the hub and physical connections is masked in the display.